\documentclass{article}

\usepackage{color}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{latexsym}
\usepackage{amsfonts}
%\usepackage{times}
\usepackage{url}
%\usepackage{bibspacing}
%\setlength{\bibspacing}{\baselineskip}
\usepackage{hyperref}
\usepackage{xspace}
\usepackage{graphicx}

\renewcommand{\L}{\mathcal{L}}
\newcommand{\V}{\mathcal{V}}
\renewcommand{\P}{\mathcal{P}}
\newcommand{\poly}{\mathrm{poly}}
\newcommand{\binary}{\{0,1\}}
\newcommand{\set}[1]{\left\{#1\right\}}

\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{propo}[thm]{Proposition}
\newtheorem{fct}[thm]{Fact}
\newtheorem{defn}[thm]{Definition}
\newtheorem{exmp}[thm]{Example}
\newtheorem{assm}[thm]{Assumption}
\newtheorem{clm}[thm]{Claim}
\newtheorem{techclm}[thm]{Technical Claim}
\newtheorem{rem}[thm]{Remark}
\newtheorem{cons}[thm]{Construction}

\newenvironment{theorem}{\begin{thm}\begin{rm}}%
{\end{rm}\end{thm}}
\newenvironment{lemma}{\begin{lem}\begin{rm}}%
{\end{rm}\end{lem}}
\newenvironment{corollary}{\begin{cor}\begin{rm}}%
{\end{rm}\end{cor}}
\newenvironment{proposition}{\begin{propo}\begin{rm}}%
{\end{rm}\end{propo}}
\newenvironment{fact}{\begin{fct}\begin{rm}}%
{\end{rm}\end{fct}}
\newenvironment{definition}{\begin{defn}\begin{em}}%
{\end{em}\end{defn}}
\newenvironment{example}{\begin{exmp}\begin{em}}%
{\end{em}\end{exmp}}
\newenvironment{assumption}{\begin{assm}\begin{em}}%
{\end{em}\end{assm}}
\newenvironment{claim}{\begin{clm}\begin{rm}}%
{\end{rm}\end{clm}}
\newenvironment{techclaim}{\begin{techclm}\begin{rm}}%
{\end{rm}\end{techclm}}
\newenvironment{remark}{\begin{rem}\begin{em}}%
{\end{em}\end{rem}}
\newenvironment{construction}{\begin{cons}\begin{em}}%
{\end{em}\end{cons}}


\newcommand{\proref}[1]{Protocol~\protect\ref{#1}}

\newenvironment{boxfig}[2]{\begin{figure}[#1]\fbox{\begin{minipage}{\linewidth}
                        \vspace{0.2em}
                        \makebox[0.025\linewidth]{}
                        \begin{minipage}{0.95\linewidth}
            {\small{
                        #2 }}
                        \end{minipage}
                        \vspace{0.2em}
                        \end{minipage}}}{\end{figure}}


\newcommand{\pprotocol}[5]{
  {\begin{figure}[#4]
      \begin{center}
        \fbox{ \small \hbox{
            \begin{minipage}{.98\linewidth}
              \begin{center}
                \textbf{#1}
              \end{center}
              #5
            \end{minipage}
          } }
        \caption{\label{#3} #2}
      \end{center}
      \vspace{-3ex}
    \end{figure}
} }


\newcommand{\protocol}[4]{
\begin{boxfig}{htbp}{
\begin{center}
{\bf #1}
\end{center}
    #4
\vspace{0.5ex} } \caption{\label{#3} #2}
\end{boxfig}
}


\begin{document}

\section{Real/Ideal Paradigm for Secure Computation}
We would like to define what it means for a protocol to be secure.  That is, if a set of participants $P_1,..., P_n$ wish to engage in a protocol, what does it mean for the protocol to be secure?  Indeed, even in the simple case of a secure channel there are several properties we could mean by security:
\begin{itemize}
\item Confidentiality: the adversary does not learn any information about the message\footnote{We'll cover what any information means in a minute.}.
\item Authenticity: the adversary cannot send messages and the sender of each message is known.
\item Anonymity: the adversary cannot learn who is sending messages
\item Non-repudiation: participants can prove to the outside world what messages were sent.
\end{itemize}
These properties are in conflict and it is not clear what is meant by ``security''.  A simulation based definition was proposed by Goldwasser and Micali in~\cite{goldwasserMicali}:

Semantic Security: We say $E$ is semantically security (SEM-CPA) for message domain $M$ and leakage function $\ell()$ if there exists a polynomial time $S$ such that for all PPT $D$ the following games are indistinguishable:
\begin{center}
\begin{tabular}{c|c}
\begin{minipage}{3in}
\begin{tabbing}
123\=123\=123\=123\=123\=\kill
\textbf{Experiment} $Exp^{\mathrm{sim}}_{E,D, S}(n)$: \\
$(pk,s_{sim}) \leftarrow S(1^n)$ \\
$(m, s_{dist})\leftarrow D(pk)$\\
$c\leftarrow S(s_{sim}, \ell(m))$\\
$b\leftarrow D(c, s_{dist})$
\end{tabbing} \end{minipage} &
\begin{minipage}{3in}
\begin{tabbing}
123\=123\=123\=123\=123\=\kill
\textbf{Experiment} $Exp^{\mathrm{adv}}_{E, D}(k)$: \\
$(pk,sk) \leftarrow Gen(1^k)$ \\
$(m, s_{dist})\leftarrow D(pk)$\\
$c\leftarrow Enc(pk, m)$\\
$b\leftarrow D(c, s_{dist})$
\end{tabbing} \end{minipage} 
\end{tabular}
\end{center}
Roughly, this definition says that (for some leakage function $\ell(\cdot)$) for any adversary with access to the actual protocol there is a simulator that is able to produce an indistinguishable view with access to only $\ell(\cdot)$.  A similar flavor of definition exists in zero-knowledge proofs~\cite{goldwasserMR85}.  We say a protocol $\pi$ is zero-knowledge if for all PPT verifiers $V^*$ there exists a $PPT\, S$ such that $\forall (x,w)\in R, \forall z$
\[
[P, V^*]((x,w),(x, z))_2 \approx S(x, z)
\]
Roughly this definition says that anything the verifier can learn by interacting with the prover can be learned by a simulator without this interaction.  The only bit of information learned is whether $x\in L$.  Thus, these two applications give an intuition that we can expand to general applications.  Roughly, we would like to say that a protocol is secure if there is some other world where a simulator receives a well-defined set of information and it is impossible to tell which world is being executed.  We will call this a trusted party paradigm.

\subsection{Trusted-party paradigm}
We'll begin by defining the trusted-party paradigm and then discuss concerns covered by the paradigm.  Let $f(\cdot, ..., \cdot)$ be a formal specification and let $\pi$ be a protocol that implements $f$.  We define the ideal world as the following steps:
\begin{enumerate}
\item Initialize parties $P_1,..., P_n$
\item Each party provides an input $x_i$ to $\mathcal{F}$
\item $\mathcal{F}$ computes $(y_1,..., y_n)\leftarrow f(x_1,..., x_n)$
\item $\mathcal{F}$ gives $y_i$ to party $P_i$
\end{enumerate}
We say that $\pi$ securely emulates $f$ if $\forall \, PPT\, A, \exists \, PPT\, S$ such that 
\[
[\pi(P_1, ..., P_n), A]\approx [\mathcal{F}(P_1,..., P_n), S]
\]
Thus, anything the adversary $A$ learns can be learned by $S$ interacting with an ideal functionality.  This definition allows $\mathcal{F}$ to be different from $f$, it may allow some leakage functions~($\ell(\cdot)$ in the case of semantic security of encryption).  However, these functions are explicit and it is clear what the simulator can learn.  Thus, by extension we are able to measure exactly what information is being learned by the adversary.  This definition covers several desiderata:
\begin{itemize}
\item Correctness: The protocol should output the function value if all parties are acting honestly
\item Secrecy: The protocol should only allow the adversary to learn the output values of corrupted parties\footnote{We allow an adversary to send a special corrupt message where they learn a parties entire state and control that party in future steps.  We give the simulator the same power.}
\item Input fairness: No party receives output from $\mathcal{F}$ until all parties have committed to their input, thus one parties input cannot depend on another parties.  This can be seen as a special case of influencing the output of the protocol.  The adversary should only be able to influence the outcome of the function by setting inputs.
\item No side-info: We would like the parties only to have the output of the function and their input.  The only side-channel information they should be able to compute should be computable from these.  For instance, if the output is a random value no party should have a preimage of this value under a TDP.
\item Fairness: fairness says that all parties receive their outputs or no parties do.  This may or may not be covered depending on $\mathcal{F}$.  
\end{itemize}

We will consider how to implement this case in situations of increasing complexity.  In order we will cover: 1) two parties executing a single protocol 2) multiple parties executing a single protocol 3) multiple parties executing multiple protocols but only non-concurrently 4) general composition of protocols~\cite{canettiUC}.  We follow the same outline as~\cite{canettiTutorial}.

\subsection{Basic Setting - Two parties}
\subsubsection{Interactive Turing Machines}
We fill follow the interactive Turing machine (ITM) model of computation from~\cite{goldwasserMR85}.  An interactive Turing machine is a standard Turing machine with three tapes: 1) \textbf{input tape} 2) \textbf{incoming communication tape} 3) \textbf{subroutine output tape}.  The input tape provides the initial input provided by the ``calling'' Turing machine.  the subroutine output tape allows ``called'' Turing machines to write back up the stack.  The communication tape allows for multiple ITMs to interact ``over-the-network''.  The communication is performed by assigning each ITM a unique address~(perhaps more than one) describing a set of addresses of permitted destinations for each ITM.  This is know s the \textbf{control function}.  Finally, we provide a \textbf{global input} to all instances.

We say that a ITM $M$ is polynomial time if there exists a polynomial $p(\cdot)$ such that the steps taken by $M$ is at most $p(n)$ where $n$ is the difference between the input bits to $M$ and the bits it writes on input tapes to other ITMs.  This prevents recursion where each machine in the stack performs a polynomial number of operations but the overall number of operations of exponential.  Indeed if all ITMs run in polynomial time, then the system of communicating ITMs completes in polynomial time in the overall inputs.

We now define a protocol as an ITM.  This will contain code for each participant and initiate each ITM.

\subsubsection{Two party security}
Consider a two-party protocol $\pi$.  We will assume an environment $\mathcal{E}$ adversary $\mathcal{A}$, and an entity $P$ that honestly runs the protocol $\pi$.  The execution is as follows

\begin{enumerate}
\item $\mathcal{E}$ is initiated with its input.
\item $\mathcal{A}$ provides inputs to $\mathcal{A}$ and $P$.
\item $\mathcal{E}$ activates either $\mathcal{A}$ or $P$ which runs until they activate the other party~(or an output provided to $\mathcal{E}$).
\item $\mathcal{A}, P$ continue until both parties write outputs to $\mathcal{E}$.
\end{enumerate}

We denote this process as $EXEC_{\pi, \mathcal{A, E}}(x)$ where $x$ is the initial input of $\mathcal{E}$.

We now describe the ideal process.  Let $f$ be a (possibly randomized) function $f:(\{0,1\}^*)^2\rightarrow (\{0,1\}^*)^2$ to be evaluated.  We add an additional entity to the system $\mathcal{T}_f$.  $P$ now runs the following protocol, when it receives its input value it forwards it to $\mathcal{T}_f$ when it receives an output from $\mathcal{T}_f$ it forwards this value to $\mathcal{E}$.  $\mathcal{T}_f$ does the following, when it receives both inputs it computes the function $f$ and returns the output value to $\mathcal{A}$ and upon receiving okay from $\mathcal{A}$ gives the output value to $p$\footnote{We can allow the adversary to have additional powers over the trusted functionality as well.  These will not be necessary in the two party setting but become important in more general settings.}.  We denote this interaction as $IDEAL_{f,\mathcal{A}, \mathcal{E}}(x)$.

\begin{definition}
A two-party protocol $\pi$ is securely evaluates $f$ if for any $PT$ adversary $\mathcal{A}$ there exists a PT adversary $S$ such that for all $PT$ environments $\mathcal{E}$ that output only one bit:
\[
IDEAL_{f,S,\mathcal{E}}\approx EXEC_{\pi, \mathcal{A}, \mathcal{E}}
\]
\end{definition}

Intuitively, this definition says that any bad behavior caused by $\mathcal{A}$ must be reproducible by $\mathcal{S}$ when interacting only with the ideal functionality.  Note that $\mathcal{S}$ must select its input before seeing any output.  $\mathcal{E}$ may provide some side information to $\mathcal{A}$ about $P$'s input and security must hold in this case as well.  Our definition does not satisfy fairness as $\mathcal{A}$ always decides if $P$ receives its output.
\begin{itemize}
\item Database intersection
\item Common Randomness
\item Zero knowledge.  The definition given is for a ZKPoK and is only secure against computationally bounded provers.
\end{itemize}
\subsection{Basic Setting - Multiple parties}
Having consider the two-party setting, we now consider the case of multiparty tasks.  The largest change is that the adversary is now a separate party instead of a participant.  All participants may only send their messages to $\mathcal{A}$ which are delivered at $\mathcal{A}$'s behest.  Furthermore, we allow $\mathcal{A}$ to send a special $\mathtt{corrupt}$ message to any participant $P_i$.  At this point $\mathcal{A}$ receives all of $P_i$ current state and sends messages as $P_i$ for the remainder of the protocol\footnote{We can consider honest but curious corruptions where $\mathcal{A}$ learns all the state of $P_i$ but $P_i$ continues to run the protocol.}.  In this section we only consider a single execution of a single protocol.

We have several extensions to the previous model:
\begin{itemize}
\item There is not a fixed number of participants.  The number of participants may grow with the execution of the protocol.  We allow any ITM to issue a ``create new'' instruction.  We also need an identity tape so participants can address each other.  The identity is specified by the creating ITI.
\item We consider multiple input/output stages.  That is, $\mathcal{E}$ may write multiple times to the input tapes of $P_1,..., $ and read multiple outputs from each party.  However, we only allow one input and one output interaction between $\mathcal{A}$ and $\mathcal{E}$.
\item We now allow the ideal machine to run arbitrary code~(since we have multiple output stages).  We further allow it to interact directly with the adversary.  Its entire code is considered the \texttt{ideal functionality} of the protocol.
\end{itemize}
\begin{definition}(Protocol emulation with basic security)  A protocol $\pi$ emulates protocol $\phi$ if for any $PT$ adversary $\mathcal{A}$ there exists a $PT$ adversary $\mathcal{S}$ such that for all $PT$ environments $\mathcal{E}$ that output only one bit:
\[
\mathtt{EXEC}_{\phi, \mathcal{S, E}}\approx\mathtt{EXEC}_{\pi, \mathcal{A, E}}
\]
\end{definition}
\begin{definition}(Realizing functionalities with basic security) A protocol $\pi$ realizes an ideal functionality $\mathcal{F}$ if $\pi$ emulates $\mathcal{I_F}$\footnote{$\mathcal{I}$ is simply the machine upon receiving an input value copies it to $\mathcal{F}$ and upon receiving an output value forwards it to $\mathcal{E}$.}, the ideal protocol for $\mathcal{F}$
A p
\end{definition}
Note that these definitions are not symmetric, a protocol $\phi$ emulating $\pi$ does not imply that $\pi$ emulates $\phi$.

\textbf{Notes} The modeling of $\mathcal{A}$ as a single centralized adversary is something of a limitation and may not reflect reality.  However, it is significantly simpler.  The ideal process is allowed some interaction with $\mathcal{A}$, the types of interaction are very important here.  If this interaction is too limited then $\mathcal{S}$ cannot emulate $\mathcal{A}$, if the interaction is too open then security is vacuous.  Designing $\mathcal{F}$ is an important part of a protocol designer's job.

\textbf{Examples:}
\begin{itemize}
\item Commitment
\item Key Exchange
\item Byzantine Agreement
\end{itemize}
\subsubsection{Feasibility}
The protocol of~\cite{yao1986} provides security in the two party sense where corruptions are honest but curious.  The protocol of ~\cite{GoldreichMW87} generalizes for multi parties as well as arbitrary corruptions.  However, neither Yao or Goldreich, Micali and Wigderson handle the issue of multiple protocols executing together.
\subsection{Issues with concurrence}
In this section, we briefly consider the issues that arise when protocols are composed.  The most intuition application is key exchange.  Generally, the purpose of a key exchange protocol is to execute secure communication with another party.
\subsubsection{Key Exchange and Secure Communication}
Let $\pi$ be a key exchange protocol that is secure in the standalone setting.  We create a protocol $\pi'$ with an additional step: after $key$ has been generated, if a message is received containing $key$, output $1$, otherwise output $0$.  Since, an adversary $A$ has a negligible chance of knowing $key$ this protocol is still secure.  However, as soon as we compose with an encryption scheme security may be lost.  We consider a simple one-time pad encryption scheme with one of two possible messages~(known to the adversary).  Then the adversary can guess one of the messages~(thus guessing the key) and use the protocol $\pi'$ to confirm their guess.  This allows them to learn both the message and key.

\subsubsection{Concurrent Zero-Knowledge}
We consider this example in very general terms.  We consider a zero-knowledge protocol $\pi$ for a language $L$.  We augment this protocol with the following two steps:

\begin{itemize}
\item $P$ shows $V$ the solution to some computational hard puzzle $p$
\item $P$ and $V$ interact through protocol $\pi$.
\item If $V$ presents a solution to some computational hard puzzle $p'\neq p$, $P$ outputs $w$.
\end{itemize}

If we assume there are computational puzzles that are easy for the prover but hard for the verifier, this should remain a secure zero-knowledge protocol in the standalone setting.  However, as soon as a verifier is able to interact with multiple provers $P, P'$ they can use the puzzle from one prover in the other prover's interaction and learn the witness in each instantiation.

\subsubsection{Malleability of commitment}
We consider an auction setting where two committers $C, C'$ wish to commit in secret on a bid for an item.  The committer with the higher committed price wins the auction.  We consider the commitment scheme of Pederson~\cite{Pedersen:1992fk}.  Here a commitment to $x$ is $com(x) = g^xh^r\mod p$ for generators $g, h$ of $\mathbb{Z}_p$.  Open simply reveals the two values $x, r$.  This is a secure commitment scheme.  However, it is clear that when $C$ commits to $y = g^xh^r$, it is possible to $C'$ to commit to a value $y'= yg$.  Once $C$ opens their commitment, it is possible for $C'$ to open their commitment~(they simply need the value $r$).  Thus, the second person to commit is always able to win the auction.

\subsection{Types of Composition}
We can consider several different ways that protocols can be composed:
\begin{itemize}
\item Timing composition
\subitem Sequential composition: no two messages of a different protocol executions are interleaved.
\subitem Non-concurrent composition: a protocol may call a subprotocol which runs to completion.  No messages from the outer protocol are sent while the inner protocol is executing.
\subitem Parallel composition: a single protocol is executed multiple times.  Furthermore, the executions are split into rounds all the messages for a single round are sent before the next round begins.
\subitem Concurrent composition: Arbitrary interleaving of protocol messages.
\item Input coordination: how are inputs related between protocol executions
\subitem Same input: each protocol has the same input.
\subitem Fixed input: the environment must specify all inputs before any protocol begins.
\subitem Adaptively chosen inputs: inputs to parties are chosen adaptively based on the state of the system.
\item Protocol Coordination:
\subitem Self-composition: only a single protocol is executed, perhaps multiple times.  This can also be thought of as a fixed number of protocols executed~(as they may all be coded into a single program ahead of time).
\subitem General composition: the protocols to be run may be determined adaptively in response to the current state of the system.
\item State coordination:
\subitem Independent state: variables for a single protocol are not seen by other protocols.  Inputs may depend on outputs of other protocols.
\subitem Joint state: specific state variables may be present in multiple protocols.
\item Number of executions
\subitem Fixed number of executions: each time the system is initiated the number of executions is known
\subitem Bounded number of executions: the system is known not to initiate more than a bounded number of executions
\subitem Unbounded number of executions: number of executions is chosen adaptively.
\end{itemize}
While most of these combinations yield meaningful definitions some combinations have received more attention in the literature.  See~\cite{canettiTutorial} for a survey of prior work.  The most general model is universal composition proposed by Canetti~\cite{canettiUC} and it captures most of the above situations.

\subsection{Univeral Composition}
We consider a model with a protocol $\rho$.  The instructions for each party provide instructions for input to some subroutine $\phi$ and instructions for when $\phi$ generates output.  We then consider a composed protocol.  Let $\pi$ be another protocol, we denote the composed protocol $\rho^{\pi/\phi}$ when each instance of $\phi$ is replaced by $\pi$.  This definition makes sense regardless of the number of invocations of $\phi$.  We can capture many settings in this model.  If we want the same-input setting each $\phi$ must run on the same input.  General composition is achieved by arbitrary $\rho$.  We consider $\phi$ as the ``formal'' specification while $\pi$ is the actual implementation.
\begin{definition}
Protocol $\pi$ emulates an ideal protocol $\phi$ with $\rho$-composable security if it holds that $\rho^{\pi/\phi}$ emulates $\rho$.
\end{definition}
We call the special case where $\rho$ is arbitrary \emph{universal composition}.  See~\cite{canettiTutorial} for more information on when protocols can be composed.
\bibliographystyle{plain}
\bibliography{crypto}
\end{document}
